﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int len = p.size(), length = s.size();
        int hash[30] = { 0 };
        int left = 0, right = 0;
        for (auto e : p)
        {
            hash[e - 'a']++;
        }
        while (right < length)
        {
            hash[s[right] - 'a']--;
            if (hash[s[right] - 'a'] < 0)
            {
                while (hash[s[right] - 'a'] < 0)
                {
                    hash[s[left] - 'a']++;
                    left++;
                }
            }
            else if (hash[s[right] - 'a'] == 0)
            {
                if (right - left + 1 == len)
                {
                    ret.push_back(left);
                    hash[s[left++] - 'a']++;
                }
            }
            right++;
        }
        return ret;
    }
};

int main()
{
    string s = "cbaebabacd", p = "abc";
    vector<int> ret = Solution().findAnagrams(s, p);
    for (auto& ch : ret)
    {
        cout << ch << endl;
    }
    return 0;
}